package club.xiaojiawei.greedy;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 5/26/22 4:51 PM
 * @question 45. 跳跃游戏 II
 * @description 给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
 * 假设你总是可以到达数组的最后一个位置
 */
public class Jump45 {

    public static void main(String[] args) {
        Jump45 test = new Jump45();
        int result = test.jump5(new int[]{5,6,4,4,6,9,4,4,7,4,4,8,2,6,8,1,5,9,6,5,2,7,9,7,9,6,9,4,1,6,8,8,4,4,2,0,3,8,5});
        System.out.println("最小步数："+result);
    }

    /**
     * 朴素法-超时
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if (nums.length < 3){
            return nums.length - 1;
        }
        recursion(nums, 0);
        return min;
    }

    int count = 0;

    int min = Integer.MAX_VALUE;

    public void recursion(int[] nums, int index){
        if (index + 1 >= nums.length){
            min = Math.min(min, count);
            return;
        }
        int step = nums[index];
        for (int i = step; i > 0; i--) {
            count++;
            recursion(nums, index + i);
            count--;
        }
    }

    /**
     * dp
     * 时间复杂度O(n^2)
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {
        int length = nums.length;
        if (nums.length < 3){
            return nums.length - 1;
        }
        int[] steps = new int[length];
        for (int i = 1; i < length; i++){
            steps[i] = Integer.MAX_VALUE;
        }
        int rear, step;
        for (int i = 0; i < length; i++) {
            rear = i + nums[i];
            step = steps[i] + 1;
            for (int j = i + 1; j <= rear && j < length; j++){
                if (step < steps[j]){
                    steps[j] = step;
                }
            }
        }
        return steps[length - 1];
    }

    /**
     * 官方-反向查找出发位置
     * 时间复杂度O(n^2)
     * @param nums
     * @return
     */
    public int jump3(int[] nums) {
        int position = nums.length - 1;
        int steps = 0;
        while (position > 0) {
            for (int i = 0; i < position; i++) {
                if (i + nums[i] >= position) {
                    position = i;
                    steps++;
                    break;
                }
            }
        }
        return steps;
    }

    /**
     * 正向查找可到达的最大位置
     * 时间复杂度O(n)
     * @param nums
     * @return
     */
    public int jump4(int[] nums) {
        int length = nums.length;
        int end = 0;
        int maxPosition = 0;
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {
                end = maxPosition;
                steps++;
            }
        }
        return steps;
    }

    /**
     * 民间-
     * @param nums
     * @return
     */
    public int jump5(int[] nums) {
        int size=0;//步数
        int presentPosition=0;
        int endPosition=nums.length-1;
        //循环判断当前位置是否可以跳到最后位置
        if (nums.length<=1){
            return size;
        }
        if (nums[0]>=endPosition){
            ++size;
            return size;
        }
        while (nums[presentPosition]<endPosition-presentPosition){
            size++;
            //,
            if (nums[presentPosition]==1) {
                presentPosition ++;
                continue;
            }
            presentPosition=selectNextPosite(nums,presentPosition,endPosition,size);
        }
        size++;
        return size;
    }
    public int selectNextPosite(int[] nums ,int presentPosition, int endPosition,int size){
        //
        int count=0;
        int tempPosition=0;

        for (int i = 0; i <=nums[presentPosition]&&i+presentPosition<nums.length; i++) {
            if (count<nums[presentPosition+i]+i){
                count=nums[presentPosition+i]+i;
                tempPosition=presentPosition+i;
            }
        }
        presentPosition=tempPosition;
        return presentPosition;
    }
}
